00100	Computer visual perception concerns visual systems for function of an
00200	organism such as a robot. We want to manipulate or avoid objects, not
00300	just  classify  them.   Thus,  we  need  their spatial relations, and
00400	three-dimensional interpretations.  A typical task is:   describe the
00500	bodies  in  a  scene,  and  describe their relations.   The choice of
00600	problems is important in the  evolution  of  a  discipline;  for  our
00700	purposes,   the   character   recognition   paradigm  is  inadequate,
00800	suggesting the wrong value judgments.
00900	
01000	Why should we  be  concerned  with  research  in  visual  perception?
01100	Because  of  its enormous implications for productivity.   Because of
01200	the importance of such problems in AI, learning and computer  science
01300	in  general.    And because of the significance for the understanding
01400	of biological systems.  Many of us now  believe  that  robotics  will
01500	ultimately transform much of industry; we cannot estimate how rapidly
01600	this change will happen, but we expect a beginning within  a  decade,
01700	and  considerable  effect  over  a  few decades.    Initially, touch,
01800	simple  vision  and  computer  control  can   incrementally   improve
01900	industrial  manipulators which now have no sensing and no contingency
02000	actions.  In the industrial context,  visual  feedback  functions  in
02100	constrained  situations,  with  known  objects  and  background,  and
02200	approximately known position and orientation, for alignment of screws
02300	with  holes, mating surfaces, etc.      Not only is this problem area
02400	of technological importance, but visual feedback is a useful paradigm
02500	for  research.         Current  efforts  in  artificial  intelligence
02600	concentrate on goal-oriented visual systems which take  advantage  of
02700	knowledge of the environment.
02800	
02900	Even  if  programming  of  robots  is  difficult,  there will be many
03000	applications  for  which  it  is  useful  to  stockpile  programs  of
03100	production  operations  rather than stockpile parts. But for ultimate
03200	impact, the programming of assembly devices must be made  simple  and
03300	rapid.   Programming  an  assembly  robot  can  be  done on a central
03400	time-sharing computer  facility  with  large  memory,  file  storage,
03500	advanced  languages  and  graphics.  That system could be an internal
03600	system for scheduling and production control, or an external service.
03700	Thus,  the whole of AI research is available for application, and the
03800	most sophisticated robotics research is relevant.
03900	
04000	But on a broader scale, the computerization of industry  will  affect
04100	production  on a shorter time scale and equally profoundly.       The
04200	problems under consideration in AI and the representations  of  shape
04300	and  space  which are evolving, have great relevance to the impact of
04400	information science on production.            The  most  far-reaching
04500	consequences  will  come  from  intellectual economies of scale which
04600	follow from systematizing production control, from modularization and
04700	commonality   of   parts  and  operations,  typified  by  the  "group
04800	technology" approach of Opits.  In this analysis, parts are coded  by
04900	descriptors;  facilities  are reorganized to produce similar elements
05000	in the same facilities.   More generally, the availability of  design
05100	records  makes possible identification of common parts and processes,
05200	and possibility for redesign.   These abilities rest upon  facilities
05300	for   design   automation,   description   of   parts   and  objects,
05400	communication  and  filing,  scheduling,  routing,  and  sensing  and
05500	monitoring  of  production.   In  these  tasks and the programming of
05600	assembly robots, representation  and  description  of  objects  is  a
05700	problem of great importance.
05800	
     

00100	Roberts [] work opened the field and set several important directions
00200	for future research:
00300		the  problem  chosen  was  perception  of   three-
00400			dimensional  objects;
00500		a  complete  system  went  from image input to display
00600			of internal descriptions;
00700		descriptions of objects were built up from volume
00800			models, a block, a  wedge,  and  a  hexagonal  prism.
00900	The  system assumed it would first obtain perfect line drawings, then
01000	interpret them.  A number of passes transformed line fragments  based
01100	on the gradient into chains of fragments, extended in both directions
01200	by sequential rms line fit which segmented at corners.  Lines  ending
01300	near  other lines were joined at vertices.  Model points were matched
01400	with  topologically  equivalent  image   vertices   by   translation,
01500	rotation, and scaling, followed by a perspective camera transform.
01600	
01700	That  system  organization  has  proven inadequate in usual cases. In
01800	other studies, such techniques encounter difficulties at every  stage
01900	of  the  sequence: lines for which no fragments are found, lines from
02000	shadows and reflections, garbled line  drawings  from  gradient  data
02100	that  look  adequate  to the eye, errors compounded at each pass. How
02200	can we improve the versatility and reliability of such a  system?  It
02300	is  not  enough to improve the individual modules themselves; so long
02400	as errors compound, only perfect modules will do.   Instead,  a)  use
02500	partial  results  to guess new tests; for example, at vertices, check
02600	to see whether one line continues; or  guess  missing  lines  from  a
02700	partial  line  drawing  and  verify.  b) use high level knowledge and
02800	models to aid the low-level operation. c) use a  variety  of  sensory
02900	information  to  determine  consistency  or contradiction. Use color,
03000	stereo, motion, shading.  d)improve  the  modules.  The  first  three
03100	provide  alternatives,  and  thus require decisions of consistency or
03200	contradiction.
03500	
03600	Minsky and Papert [Minsky 1972] have described the central issues and
03700	relevance of vision in artificial intelligence.  Some primary issues
03800	are:
03900		symbolic descriptions of facts and procedures
04000		manipulation of descriptions
04100		heterarchical control structures.
04200	Heterarchical systems are still in evolution; the aim of such systems
04300	is to break the pass-oriented structure of systems such as described
04400	above, to involve knowledge from the high level to guide low-level
04500	operations, and use partial knowledge at any phase of perception to
04600	draw hypotheses which control subsequent perception.  Winston []
04700	has described some desiderata for such systems.  Some examples appear
04800	later.
04900	
     

00100	Roberts used concavities and T vertices  to  guess  at  obscured  and
00200	unobscured  faces of plane-faced objects. Guzman went beyond matching
00300	models and  was  able  to  separate  objects  in  complex  scenes  of
00400	plane-faced objects. He used local evidence from Y and arrow vertices
00500	to link regions which might belong to the same body.   Regions linked
00600	twice  were  joined  into  bodies;  any regions linked twice to these
00700	clusters of regions were also joined, etc.   Double  linking  reduced
00800	the error rate but missed some regions which should have been joined.
00900	Some were joined by another step, uniting regions linked only to  one
01000	other  region.  Although it was not stated thus, links were formed at
01100	vertices  with  three  lines  if  they  were  not  a  T   (indicating
01200	obscuration), between those regions without concavities at the vertex
01300	(some were inhibited using knowledge about the  background  given  by
01400	the  user).   Eentually, a refinement was added to inhibit links when
01500	the next vertex along the common edge is concave or colinear for  one
01600	of  the  regions.   Thus, the program was heavily based on concavity.
01700	All but two of the objects used by Guzman were right prisms, so  that
01800	special  case  techniques  could  have  worked well. Other links were
01900	introduced, without much motivation.    It did surprisingly well, but
02000	had   problems   with  holes  and  other  non-convexities,  and  with
02100	accidental alignment. It depended on being told the  background,  and
02200	the  techniques did not extend very far, despite considerable effort.
02300	The program was based on some well-motivated ideas, but they formed a
02400	recipe,  not  an  understanding of the problem.  Among the extensions
02500	were  Orban's  program  to  remove  shadows  from  a   scene,   using
02600	observations about peculiarities of shadow vertices, sequences of L's
02700	and X's.  Rattner introduced some vertex types unused  by  Guzman  as
02800	splitting  vertices  for separating bodies.   Winston used the output
02900	of Guzman's program to find relationships of above, below,  in  front
03000	of, left and right.
03100	
03200	Huffman  and  Clowes  independently  analyzed trihedral vertices seen
03300	from non-singular perspective (no  infinitesimal  change  of  viewing
03400	position  would  change  the number of visible lines); by classifying
03500	the edges as convex, concave, and  obscuring,  they  could  enumerate
03600	just  12  such vertices.  For isolated objects with known background,
03700	it was possible to get labellings for possible  objects,  and  reject
03800	some  drawings  as  impossible  under  the  assumptions.   Some other
03900	interesting results were obtained.
04000	
04100	Falk's work combined features of Roberts and Guzman's  programs.   He
04200	made  a body segmentation based on heuristic such as Guzman used, but
04300	instead of collecting regions  into  bodies,  he  joined  lines  into
04400	bodies.  Since  missing  edges  cause  regions to be non-planar, some
04500	errors made by joining regions were avoided.  Support  and  occlusion
04600	were  determined  by  heuristics  from  the  body  edges.  Edges were
04700	extended to complete faces if possible.  Objects were matched against
04800	a  set  of  models  by  first  choosing objects whose support was the
04900	table, and using their known size to compare with models having fixed
05000	sizes.   Then  other  objects'  sizes were determined from successive
05100	support relations.  Hidden line elimination techniques were  used  to
05200	test  whether  the fit was adequate, and whether missing lines should
05300	be predicted for verification.
05400	
05500	
05600	Waltz  expanded  that  labelling  of lines to include convex,concave,
05700	convex obscuring, crack, shadow, and concave  obscuring.   Each  line
05800	was labelled according to the illumination: illuminate, self-shadowed
05900	(facing away from the source), shadowed by obscuration.  Of the  many
06000	possibilities  for  the  lines at a vertex, only a small fraction are
06100	actually consistent.  Many fewer  interpretations  are  possible  for
06200	which  adjacent  vertices  have consistent interpretations for shared
06300	lines.     It  would  seem  that  such  large  numbers  of   possible
06400	interpretations   would   be   unmanagable;  instead,  the  increased
06500	precision of descriptions  allows  very  rapid  discarding  of  wrong
06600	interpretations, so that the process allows very quick solutions. The
06700	procedure was initially  regarded  as  a  tree  search;  however,  an
06800	initial  filtering  was  introduced  to  minimize  the  combinatorial
06900	explosion of the search process.  The  filter  process  consisted  of
07000	taking  the  intersection  of  the  possible  labels for common lines
07100	between any two vertices.  The filter process in itself was  adequate
07200	without  the  tree search.  The process is reasonably fast, and finds
07300	all interpretations; some heuristic preference rules  allow  choosing
07400	most  reasonable interpretations. The program succeeds with holes and
07500	shadows.   It does depend on being told which regions are the  table;
07600	it  is  not  clear how important that limitation is. The program does
07700	give a good analytic understanding of  the  process  of  interpreting
07800	line drawings, and represents a significant advance.
07900	
     

00100			LEARNING
00200	
00300	Learning is description.  The ideas of learning current in computer
00400	perception differ from those of pattern recognition or game playing,
00500	which might be called statistical learning.  The paradigm in statistical
00600	learning is that given enough trials, the weights of some coefficients
00700	will slowly change to values which minimize some loss function.  The
00800	model for learning which is current in machine perception is that
00900	learning is building and manipulating descriptions.  The descriptions
01000	are symbolic; the function of training samples is very different.
01100	from that of statistical learning.  Here, one sample may cause a
01200	qualitative change in the description; the function of a teacher is
01300	to choose examples which guide the formation of descriptions.  
01400	Winston [] has demonstrated a learning program which uses descriptions
01500	of line drawings of polyhedra.  Relations including supports/supported-by,
01600	left-of/right-of, in-front-of/behind, abuts, combined with object
01700	names for block, wedge, are used for graph structured descriptions.
01800	Set membership and must-have/must-not-have modifiers for relations are
01900	elements in the description.  An essential element is a "near-miss"
02000	example.  Given a model of a geometric structure, eg an arch, the
02100	machine is given an example of a non-arch, with the supports contacting.
02200	The model is contrasted with the description of the near-miss, a
02300	difference description is constructed, and the important difference
02400	is guessed by heuristics.  
02500	In this case, the model is modified to include the condition that the
02600	supports must not contact.  Grouping relations are added to increase
02700	the power of the descriptive mechanism.
     

00100	For  what sorts of scenes can current programs obtain reasonable line
00200	drawings?         For scenes of untextured polyhedra.    What are the
00300	problems?  There are problems at corners and wherever high resolution
00400	is  necessary,  with  segmenting  of  curved  edges,  with   textured
00500	surfaces, with speed, and with adequate sensors.    What improvements
00600	are possible? Better use of high level knowledge, use of organization
00700	based  on  proximity,  increased  computing  power,  better low level
00800	descriptions, better analysis of these descriptions.      We  err  in
00900	separating  the  low  level  parts  of a system which deal with image
01000	quantities (light intensities, lines, corners) from  the  high  level
01100	parts  of  a  system which deal with object descriptions. The goal of
01200	such a split is the perfect line drawing.    That is unattainable: a)
01300	Not all lines are visible easily.   Illumination may be equal on both
01400	sides  of  an  edge.    b)  Typically,  there  is  vastly  more  edge
01500	information  than  just  those  lines  which  delineate boundaries of
01600	objects.        Not  all  intensity   discontinuities   are   surface
01700	discontinuities    (shadows,    reflections,    surface    markings).
01800	Textured scenes contain enormous numbers  of  edges.        c)  given
01900	visual resources there is always a benefit in subdividing effort into
02000	general  orientation  and  warning  functions,  and   guided   foveal
02100	concentration using context for goal-directed perceptual activity.
02200	
02300	If  we  use  strictly  image  information,  we  attempt  to see light
02400	intensity discontinuities (edges) to infer  surface  discontinuities.
02500	Usually, local operators are used to find fragments of an edge (small
02600	enough to be locally straight).  Modules may also look for regions of
02700	like  points.   They must then distinguish when points are unlike the
02800	region; ie, they must detect discontinuities just as  edge  detection
02900	does.     How  can  we describe discontinuities?       They should be
03000	directional and extended. There must be a range of sizes of operators
03100	to  allow  for  both  high  resolution  features  and  low resolution
03200	features (diffuse  edges  in  xrays).      The  gradient  is  not  an
03300	adequate  measure  of discontinuity; the human visual system does not
03400	find edges at smooth gradients. There are many smooth  surfaces  with
03500	large gradients because of reflection and curvature.
03600	
03700	Roberts  used  a  gradient  operator.    Hueckel  used  a  few moment
03800	coefficients  to  fit  a  best  step,  thus  imposing  directionality
03900	conditions.  In practice, large gradients at reflections cause masses
04000	of spurious edge fragments. Binford eliminated the  gradient  problem
04100	by  subtracting  the  local  average  at  each  point,  then applying
04200	operators  in  a  few  directions   using   the   average   gradient.
04300	Bio-modeling  was  strictly  avoided,  although  that  is  similar to
04400	biological  systems.  Edges  were  extended  by  an   optimal   curve
04500	sequential  decision  process.   Each unterminated tentative edge was
04600	tested at each extension; a curve with locally maximal  contrast  was
04700	found  near  the  predicted  curve.    Continuity  of  direction  and
04800	contrast were evaluated to decide whether  to  extend  or  terminate.
04900	If  terminated,  the  contrast  of the optimal curve was evaluated to
05000	keep or discard.    If kept, the curve was backed  up  by  sequential
05100	decision  to  a  best  termination.   Its  intent  was to examine the
05200	hypothesis given by the local edge operator, and to reject or confirm
05300	by  extension.   Edges were thus extended past small gaps or portions
05400	with weak signal.    A non-linear contrast weighting was  used  which
05500	minimized  the  effect  of  small surface markings.   Thresholds were
05600	calculated in advance.
05700	
05800	Rosenfeld describes efficient gradient operators  of  various  sizes.
05900	Martelli has made an optimal curve search as a means of edge-finding;
06000	it may be useful if  we  find  adequate  descriptions  of  continuous
06100	curves for the evaluation function.
06200	
06300	Regions  can  be  defined  by brightness, color, textural properties,
06400	depth, etc.  A  region  is  surrounded  by  non-region  points  (edge
06500	points).  Thus, they resemble edge-oriented methods.  Region-oriented
06600	systems have been completed by  Binford  [],  Fenema  and  Brice  [],
06700	Barrow  [], and Krakauer [].  Most used grey level contours which are
06800	inadequate  for  the  same  reasons   as   the   gradient.    Binford
06900	[unpublished] and Bajcsy [] have made color region finders.
07000	
07100		Edge Organization
07200	
07300	It  is a long hard process to go from local edge fragments or regions
07400	to complete line drawings.  Roberts  []  passed  operators  over  the
07500	entire set of tentative edges, defining longer lines, then segmenting
07600	by line fitting.  Nearby ends of lines were linked at vertices.  Horn
07700	[]  used  similar  techniques with many improvements, particularly in
07800	vertex determination.  An edge follower has been made by Pingle [].
07900	
08000	In what way can knowledge improve this performance?   The  TOPOLOGIST
08100	proposed missing edges from partially completed drawings.  Herskovits
08200	line verifier sensitively tested such predictions.  Shirai began with
08300	scenes  for  which  the contrast of objects with background was large
08400	(black background).  At vertices, the extension of boundary lines was
08500	tested.    Internal   lines   were   tested   for.   Completions  for
08600	unterminated lines were searched for.  The use  of  context  involved
08700	not  changing thresholds, but using special-purpose operators: verify
08800	a line along at known position and angle; find termination of a line;
08900	find  a  line  through  a  point  but  with unknown angle.   The best
09000	performance is given by Shirai's system and by the Binford-Horn  line
09100	finder,  which  is  able  to  find  most  lines  without attention to
09200	lighting, in a scene of white  blocks  on  a  white  background.   It
09300	misses  a  few  lines  which  are  found by subsequent prediction and
09400	verification, and garbles some  vertices.  Shirai's  system  performs
09500	much  better.   It  requires  large  background contrast however, and
09600	misses  some  objects  for  which  no  cues  are   available.     The
09700	combination  of  the  two  allows  adequate (not necessarily perfect)
09800	construction of line drawings of polyhedra.
09900	
10000	There has been a large amount of work  on  texture  considered  as  a
10100	two-dimensional   problem,   for   agricultural   surveys  and  earth
10200	resources. Bajcsy [] has considered textures in outdoor scenes  as  a
10300	three-  dimensional  problem;  a representation for texture was made,
10400	descriptors for texture  elements  were  analyzed  from  the  Fourier
10500	transform  the  directionality,  size  and spacing of repeated linear
10600	elements  were  obtained  from  the  Fourier  transform,   and   some
10700	descriptors  were  obtained  for non-directional elements.  Color and
10800	texture regions were obtained; texture gradients and  a  world  model
10900	for  some outdoor scenes were used to explore higher level perception
11000	of these scenes.
11100	
12000	Consider orders of magnitude for computing time for a computer visual
12100	system.   Current  perception  is quite inadequate, but the low level
12200	operations require about 150 usec per point (in  machine  code  on  a
12300	PDP-10 class machine).  A typical image has 80,000 pts; multiply by 2
12400	for stereo and 2 for color to find about 50 seconds per stereo  color
12500	image  to  accomplish  edge  or  region finding over the whole image.
12600	Stereo correlation involves a minimum of 8 minutes per  color  image.
12700	Current programs are much slower than these minimum estimates. Higher
12800	level languages would be a factor of 5 slower.  The biological system
12900	does the equivalent in about 1/10 th second, or about a factor of 500
13000	faster, with a factor of 10 more  retinal  elements.   What  hardware
13100	improvements   can  we  expect  reasonably  now?   If  we  assume  10
13200	arithmetic elements with 8 bit multiply in 50 nsec,  correlation  and
13300	other  typical  low-level  operations gain a factor of 1000 in speed.
13400	That device might not be as useful for other visual operations.  Such
13500	a  device  is  not  expensive in parts, now, and is potentially quite
13600	inexpensive with large scale integration.
13700	
13800	Such increases in hardware speed are necessary; equally necessary
13900	are the increases which come from sampling and preview functions,
14000	and goal-directed activity.  Most vision eventually functions in
14100	continuous perception.  Scenes change very little; current knowledge
14200	of the scene enables intelligent choice of tracking changes with
14300	little effort, and solving problems with goal-directed activity.
     

00100		Representation
00200	
00300	
00400	We will describe work toward implementing symbolic
00500	descriptions of shape which are adequate for typical robot tasks
00600	such as manipulation, collision avoidance, display, and recognition.
00700	Although many would disagree with our criteria, the design criteria
00800	were:[]
00900	a) Representations should symbolic at a high level in order
01000	to interface with heuristics of the problem domain.
01100	b) Representations should depend on segmentation into parts,
01200	which may have subparts
01300	c) Primitives should be three-dimensional volume primitives.
01400	This is motivated by realizability of objects.
01500	d) Descriptions should be generative.  A modest collection of
01600	primitives should allow description of a vast set of objects.
01700	
01800	Figures show experimental results of computer descrition of some
01900	objects [].  They give some indication of the primitives of the
02000	representations, and their power, even with preliminary programs.
02100	The representations [Binford 1971] depend upon segmentation to
02200	describe complex objects in terms of parts.  The representations
02300	are grqph-structured. Parts are structures of the same form.
02400	The utility of these representations lies in a choice of primitives
02500	which allows a natural choice of parts.  Cutting and pasting are
02600	used in joining parts.  Primitive parts are described by
02700	"generalized local translational invariance", a formal construction
02800	for generalized cones, generalized helices, and generalized torii.
02900	The basis for the representation is the transformation of cross sections
03000	which are normal to a space curve (the axis) along which the cross
03100	sections are translated.
03200